1. TECHNICAL FIELD
This invention relates to interactive computer graphics, and more particularly to the field of bit mapped color video display.
2. DESCRIPTION OF RELATED ART AND BACKGROUND
This invention functions in a workstation with graphics display capability supporting multiple windows wherein the hardware may contain one or more hardware color look-up tables (CLUTs), and wherein the system may, in some cases, operate under the X Window System.sup.TM protocol. The "X Window System" is a Trademark of the Massachusetts Institute of Technology. In other cases, the invention may operate with other well known window systems such as Microsoft Windows.RTM. or Apple Macintosh.sup.TM Windows. "Microsoft" and "Microsoft Windows" are registered trademarks of Microsoft Corporation. "Apple" and "Macintosh" are trademarks of Apple Computer Inc. FIG. 1 describes generally this environment, showing the essential resource elements in an X Window System context.
The X Window System is a system supported by a dozen or more computer vendors, through a joint effort to standardize a Windowing System and is well known in the art. The X Window System defines a protocol (the "X Protocol") for handling multiple window display demands. The X Protocol provides for dealing with multiple applications ("clients") which wish to display a window on a video screen regardless of whether the client is local or on a remote host or workstation communicating through a network. The X Protocol also allows for a client to use his own colormap, in an environment that has n hardware color look-up tables (CLUTs), where n=1 or more. A "colormap" is a set of color values used to display colors on a screen and is more fully described below. Most hardware workstations presently support only one hardware color look-up table (CLUT). A general description of the rules used and the operation of the Version 11, X Window System Server (the "X11 Server") in handling color displays of multiple windows, including the use of color look-up tables (CLUTS) can be found in many publications on the X Window System, such as the book titled "X Window System" by Robert W. Scheifler, James Gettys and Ron Newman published by Digital Press in 1988 or "X Window System Programming" by Nabajyati Barkakati, published by SAMS, a division of Macmillan Computer Publishing, Carmel, Ind. in 1991, at pages 341 through 369.
A display screen in the X Window System has a block of memory, known as a "Frame Buffer" or "Video Memory", that is capable of storing a fixed number of bits (usually 1,4, or 8) for each Pixel (the Pixel value) on the screen. The color displayed is a function of the Red, Green, and Blue (RGB) values obtained from the colormap by means of the Pixel value. The video hardware used in most X Window System displays can use only one colormap at a time, which creates the notion of "installing" a colormap into the hardware color look-up table (CLUT).
Accordingly, the various elements depicted in FIG. 1 are generally well known in the art, but form an environment in which the present invention may function and in which the presently preferred embodiment of the disclosed invention does function. In FIG. 1, a computer display 10 containing multiple windows, with an associated keyboard 12 and mouse 14 are shown related to the elements involved in a color display system. Images which are to appear in a window on a screen are stored in a drawing or Image Data Plane Group 16 which contains pixel values and which is part of a Frame Buffer 26 (with one or more bit planes). Some attributes of the video display of the pixel, such as which CLUT is used or which plane group is used, are stored in the Display Attributes Plane Group 20 which may also be part of the Frame Buffer 26. The Display Attribute Value or Identification Value 32, when present, is typically used as an index into a Display Attribute Table 34 which contains various data including the identification of a particular hardware color look-up table (CLUT) or CLUT ID 36, where multiple CLUTs are available. The Display Attribute Identification Value 32 is sometimes called a display tag, window id, display id, or attribute id. In this discussion we shall refer to this value as a "Display Attribute Identification Value" (the "DAIV"). The color of the displayed window painted on the screen is derived from the values in a colormap stored in one of the Hardware Color Look-up Tables (CLUTs) 18, which translate pixel values into colors ( which are composed of different intensities of the primary colors: Red, Green, and Blue (RGB)).
The X Windows System encapsulates the common features of display hardware in a data structure called a "Visual", which contains all the information that characterizes the display. When a window is created an associated Visual must be specified. In the X Windows System, "Visuals" include the following classes:
"DirectColor" Visuals model the display type in which the pixel value is decomposed into bit fields that index into individual colormaps for the R, G, B components. The colormap entries can be dynamically changed. PA1 "TrueColor" Visual displays are the same as DirectColor but their colormaps are fixed. PA1 "PseudoColor" Visuals model a display hardware where each pixel value looks up an RGB value and the colormap can be modified any time. PA1 "StaticColor" Visual displays are similar to PseudoColor except that the colormap cannot be modified. PA1 "GreyScale" Visuals model a greyscale monitor that allows the intensity of the map to be modified. PA1 "StaticGrey" Visuals are similar to GreyScale but with a fixed grey level map. PA1 Neither the Voorhies et. al. paper nor the following United Stated patents address these issues. PA1 1. Provide the capability to efficiently use multiple hardware colormaps, according a defined priority of installation. PA1 2. Impact the performance of the implementation for single colormap hardware as little as possible. PA1 3. Keep the actual hardware manipulations abstracted from the Server code.
These concepts will be made clear by a more detailed summary of how color is displayed on a bit mapped display. The displays on graphical computer terminals are generated by reading a "bitmap" (i.e., a storage array of "1s" and "Os" corresponding to the intensity pattern of the screen display) and using the bits to intensity modulate the light output of the display. Each particular dot on the screen is referred to as a pixel and the intensity value for a particular dot is called the pixel value. Pixel values are commonly stored in frame buffers or video memory and may be thought of as a buffer organized in a number of bit planes with as many bit planes as there are bits in each Pixel value. The number of bits in each Pixel value (i.e. the number of bit planes used) is also known as the "depth" of the display. The number of bits allow 2.sup.4 or 16 different scale values for the image on the screen. Many more values of screen intensity can be allowed by using the Pixel value as an entry to a look-up table (LUT) of intensity values to pick the actual value to use to activate the Pixel. For example, a look-up table of 16 bit values would contain 2.sup.s =65,536 intensity values even though using the 4 bit Pixel value as an index into this look-up table would allow the use of only 2.sup.4 =16 of these 65,536 values at any one time. Raster scanned color displays represent any color by combinations of the three primary colors: Red (R), Green (G), and Blue (B). A bit mapped display converts the pixel value into light intensities by mixing three primary colors. In such color displays, the Pixel values either represent the color values (i.e., Red, Green, and Blue (RGB)) or an address in a color look-up table (CLUT) containing the RGB color values as described above. The specific list of color values stored in a color look-up table is referred to as a "colormap". In this context, we shall use the term "Colormap" (with a capital C) to refer to a Colormap Object which contains an augmented data structure (i.e. contains other data besides just the red, green, and blue values) and possibly a number of "program operators". A "Program Operator" is a set of instructions which may be thought of as causing the system to perform a specific task.
The principal function of a window system such as the X Window System is the management of hardware resources. In the X Window System, Clients (application programs) do not access the actual display hardware such as the frame buffer or the hardware color look-up table (CLUT). Instead the Client references the X Windows System objects (software constructs) "Window" and "Colormap" respectively. Each Client requests the X11 Server to render into portions of a Window that the Client owns instead of rendering directly to the Frame Buffer. The X11 Server enforces a stacking order which in turn regulates which portion of a window is visible on the display screen. Similarly, a Client allocates colors in an X Window System Colormap Object instead of directly loading the actual hardware CLUT. The pixels rendered into a window on behalf of a Client appear correctly only when the Client's colormap is installed into a CLUT via the XlnstallColormap request.
In a display system containing only one CLUT,when more than one Client requests more than one colormap for their respective applications, only those windows for which the colormap has been installed will appear correctly displayed. All other windows which do not use the currently installed colormap will have false colors displayed for all pixel values where their related colormaps differ from the colormap actually installed. This phenomenon is referred to as "flashing".
There are conventions and strategies used to insure that Clients share the hardware CLUT in a well ordered fashion leading to a reduction in flashing. The most common convention is the "Interclient Communication Conventions" (ICCCM) developed by Rosenthal.
To further alleviate the problem of "Flashing", new display hardware is being intr marketplace with more than one Hardware Color Look-up Table (CLUT). This introduces the added complexity of having to keep track of which particular hardware CLUT contains the colormap for each window. Moreover, newer hardware workstations provide multiple CLUTs with different depths. For example, a given workstation might provide for two 4-bit CLUTs and four 24-bit CLUTs. In addition, workstation hardware vendors are providing units with advanced Frame Buffers consisting of more than a single group of bit planes for holding displayed images. Some Frame Buffers have 100 or more bits per pixel divided into separate plane groups serving various functions. These plane groups may hold data (i.e. images to be displayed, overlays, and Z-buffers) or control information (i.e. hardware clipping ids and video display attribute identification values). Moreover they are large enough to allow applications to use two drawing (image) plane groups alternatively where double buffering is required (i.e. writing from one image plane group while updating the other, and then writing from the alternate plane group while updating the first). Animation type displays use such double buffering techniques. A Z-buffer is a buffer, typically of the same size as the frame buffer of the related image, which is used to specify the visible surface determination for creating realistic three dimensional (3D) images. Only windows containing 3D images require/use Z-buffers. Clipping ids are per-pixel tags which identify that part of the window image which shows on the screen. These new hardware multiple plane group features provide the resources for handling multiple complex display windows simultaneously. For example, one screen could contain the following: one window which displays an interactive 3D application in a 24-bit Red, Green, Blue (RGB) format; another window displaying an Engineering Computer Aided Design (ECAD) application in an 8-bit pseudocolor format; an interaction panel, a clock, and several icons displayed as 4-bit pseudocolor windows. This combination of multiple windows, multiple depths (i.e. number of bits in the pixel value), and multiple color displays requires that the server not only be able to manipulate the various plane groups involved, but also control the hardware CLUT resources in a way which minimizes the visible color display problems which might arise because of rapid colormap changes. While the X Window System defines a protocol for dealing with Frame Buffers which support multiple images with multiple depths, the X Protocol does not specify how to do it. The present invention is a scheme for actually managing such complicated requirements and resource combinations efficiently and in a generalized way while conforming to the general X11 Server model.
Some present systems provide a scheme whereby the actual hardware CLUT used by a pixel on the screen is determined by the pixel's Display Attribute Value and a Display Attribute Table which is indexed by the Display Attribute Value. When a hardware CLUT is allocated to a client colormap the X11 Server paints the Display Attribute Plane Groups values for all the visible pixels of a window with one Display Attribute Value and sets the table entry for that value to use a particular hardware CLUT. Referring to FIG. 2 it can be seen that the Display Attribute Plane Group 20 corresponds to the Image Data Plane Group 16 both of which are a part of the Frame Buffer 26. The Image Data Plane Group 16 contains the Pixel values to be used as an index into the proper hardware CLUT containing the desired colormap. Window A 42 is referenced in the Display Attribute Plane Group 20 by a set of locations corresponding to the Pixels which define the geometry of Window A. Each Pixel location in the Display Attribute Plane Group 20 contains a display Attribute Value 32, which is an index into the Display Attribute Table 34 to obtain the ID of the particular hardware CLUT to which the colormap of Window A is assigned.
For a device with n hardware CLUTs and n display attributes, the X11 Server could always assure that the n most recently installed X11 colormaps will display correctly. This can be done using n display attribute values, each of which is set to display a different hardware CLUT. When a colormap is being installed, the X11 Server could paint all the windows using the colormap with the Display Attribute Value set to the least recently installed hardware CLUT, thereby making this CLUT the most recently installed one.
This is a simple scheme using the fewest possible Display Attribute Values but it has the severe disadvantage of painting the Display Attribute Planes of the Frame Buffer when a colormap is installed thereby making colormap installation slower than on displays which only have a single hardware CLUT which do not require the use of the Display Attribute Planes for this purpose. In addition, display attributes are also used for other graphics functions which implies that some colormaps would need more than one Display Attribute Value. The present invention reduces the need for painting these Display Attribute Planes of the Frame Buffer whenever a private colormap is installed, by creating a Colormap Object containing the colormap data as well as other data and operators. A DAIV is allocated for each Colormap Object and the assigned hardware CLUT is kept track of in the Colormap Object itself. This saves an enormous amount of processing time since rendering of the Display Attribute Planes is not necessary.
In addition, a Multiple Hardware Colormaps (MHC) system must not simply disallow the attempted installation of a new colormap when all of the hardware CLUTs are in use. Rather a proper scheme must allow the Most Recently Installed (MRI) colormap to replace the least recently installed one with the color degradation of other windows with colormaps installed occurring gracefully. For example, this MRI policy is implied by the X Window System use of a "required list" of installed colormaps.
The Prior Art does not address these issues or imply an appropriate solution to the efficient handling of multiple hardware colormaps. A scheme for using a display attribute tag ( also called an index or attribute value) with an associated display attribute table to manage multiple hardware color look-up tables (CLUTs) is disclosed by Douglas Voorhies, David Kirk, and Olin Lathrop in a paper titled "Virtual Graphics" found in the Association of Computing Machinery, Proceedings of the Special Interest Group on Computer Graphics held in 1988 (SIGGRAPH 88) on pages 247 through 253. Referring to FIG. 3, the authors (on page 251 ) state that the actual number of windows is not limited by the display attribute table size 44 (16 entries in their example) "since several windows will often share the same attributes." The authors further state that the actual number of CLUTs 46 (8 in their example) is not a limitation since windows may share CLUTs or CLUT blocks. Consequently the authors disclose no method for controlling the assignment of these tags (display attribute identification values or indices) nor any scheme for managing the sharing of such display attribute identification values (or DAIVs as we call them herein) between windows with different colormaps. Moreover, regarding sharing of CLUTs or CLUT blocks, even when a 256 entry CLUT, for example, is divided into blocks of less than 256 colors, the problem remains of how to manage the blocks and block assignments themselves. Some hardware designs index fixed size blocks of color in a single CLUT with other bits which can be considered an extension of the display attribute. U.S. Pat. No. 4,772,881 Hannah (1988) discloses such a scheme. Experience has shown that severe degradation of performance and color flashing can occur when these Display Attribute Identification Value assignments are not managed and controlled, especially in the more advanced workstation environments described above.
Priem et. al. U.S. Pat. No. 4,958,146 (1990) defines a multiplexer implementation of circuitry for performing Boolean Raster operations in a workstation whose functions include the display of graphic images using multiple planes and having foreground and background colors.
Yamamuro et. al. U.S. Pat. No. 4,908,610 (1990) defines a scheme for converting compressed color data in a graphics processor into uncompressed color data for storage in a frame buffer prior to usage for screen display.
Takashima U.S. Pat. No. 4,853,681 (1989) defines a hardware image frame composing circuit for early detection of a color value of transparency in a plurality of color look-up tables (CLUTs) in order to minimize the circuit size and insure the inherent delays do not impact the variety of colors available when high clock frequencies are used.
Van Aken et. al. U.S. Pat. No. 4,799,053 (1989) defines a scheme for both loading color values into the Color look-up table (CLUT) and recalling colors from the CLUT for use in video displays using a single set of address and data channels for both loading and look-up.
Work et. al. U.S. Pat. No. 4,769,632 (1988) discloses a color graphics control system, which may be incorporated in a single integrated chip, for generating electrical signal values for respective color inputs to a raster scan color display unit in response to a succession of pixel values derived from a pixel memory device, and using a color look-up table for obtaining the color values.
Hannah U.S. Pat. No. 4,772,881 (1988) discloses a method for using additional bits of data in the pixel value in the frame buffer to provide a way to designate different color values in a given color look-up table (CLUT) for the same pixel value. However this patent does not discuss methods for assigning and controlling these additional bits of data or for their use with multiple color look-up tables.
None of these patents individually or in combination read on the disclosed invention.